package de.saar.penguin.give2.server;

import java.util.*;
import give.world.*;
import give.formula.*;

/**
 * This Class is a first implementation of a Referring Expressions generator
 * @author Boris Fersing
 */
public class REgen {

	/**
	 * Enum type Determiner
	 * It stands for the article.
	 * 
	 * THE - It should be issued when the target is known or unique. So far, it's the only case.
	 * 
	 * A - probably we will need it in case if we will implement the pre-order instruction generation
	 * (you'll go to the next room and press there a blue button)
	 * 
	 * There probably should be another values (THIS, THAT, ANOTHER).
	 *  
	 * @author Olga Nikitina
	 * 
	 * 
	 */

	private enum Determiner {
		THE("the"), A("a");

		private final String art;

		/*
		 * A contructor.
		 */
		Determiner(String art){
			this.art = art;
		}

		/*
		 * A method for getting an article from the enum type.
		 */
		public String getArt() {
			return this.art;
		}
	}
	/* Fields in this class:
	 * relexp - position in the group that describes the target uniquely (i.e. the right button)
	 * It is set in the methods checkRelPos and checkRelPosDoors
	 * 
	 * closeObjects - a set of buttons that form a group
	 * It is computed in the method fillInCloseObjects
	 * 
	 * closeDoors - a set of doors that form a group
	 * It is computed in the method fillInCloseDoors
	 * 
	 * buttonTime - a marker that prevents buttons from being used as landmarks until other objects are available.
	 * It is changed inside the method olgarithm, when constructing RE (=referring expression) for a button target.
	 */
	private String relexp = "";
	private ArrayList<String> closeObjects = new ArrayList<String>();
	private ArrayList<String> closeDoors = new ArrayList<String>();
	private boolean buttonTime = false;

	/**
	 *  Method generateRE(former olgarithm).
	 *  (RE = referring expression)
	 * 
	 * @param describedObjects
	 * 			All described objects in the world.
	 * 
	 * @param target
	 * 			The target object to which we want to refer.
	 * 
	 * @param visibleObjects
	 * 			The set of currently visible objects.
	 * 
	 * @return
	 * 			The method returns refexp, a String describing the target object.
	 * 			The refexp is made of concatenated strings inside this method.
	 * 
	 * The method uses a number of smaller methods.
	 * Each of the smaller methods does the following: 
	 *  it takes one of the attributes and checks if the RE that includes only this attribute is unique or not.
	 *  The attributes and associated methods for them are:
	 *  -- type (method checkTypeAndColour);
	 *  -- colour (method checkTypeAndColour),
	 *  -- position relative to a landmark (method checkPosToLandmark),
	 *  -- position relative to the user (method checkPosToUser and part of the algorithm under the label button_close),
	 *  -- position relative to another close object of the same type (methods checkRelPos and checkRelPosDoors).
	 * 
	 * The method also uses other auxiliary methods that mostly specify the conditions of the applicability of a RE.
	 * 
	 * The method does the following:
	 * 1. check if RE that includes only type and colour of the object is unique. If yes, issue such RE.
	 * If not, different techniques will be applied to objects depending on their type.
	 * 
	 * For doors:
	 * a. check for a RE that includes the target's position relative to a landmark + target's type (i.e. the door to the left of the flower)
	 * If such RE is unique, send it.
	 * b. check for a RE that uses the target's position in a group of similar objects + target's type (i.e. the right door)
	 * If this RE is unique, send it.
	 * c. check for a RE that uses the target's position relative to the user + target's type (i.e. the door to your right)
	 * If unique, send it.
	 * If none of those are usable, the method ends its work and returns a marker that it cannot construct a unique RE ("oops")
	 * 
	 * 
	 * For buttons:
	 * a. check for a RE that includes the target's position relative to a landmark + target's colour and type (i.e. the red button to the left of the flower)
	 * If unique, send it.
	 * b. check for a RE that includes the target's position relative to another close button + target's colour and type (i.e. the red button to the left of the green one)
	 * If unique, send it.
	 * c. check for a RE that uses the target's position in the group of other buttons. (i.e. the right button in the group of 3 buttons)
	 * If unique, send it.
	 * d. check for a RE that uses the target's position relative to the user (only in terms of how close\far away the button is) (i.e. the most distant (red) button)
	 * If none of those are usable, the method ends its work and returns a marker that it cannot construct a unique RE ("oops")
	 * 
	 * For objects of other types I have nothing better than just a RE that uses only the type.
	 * But since they are never used as targets in our algorithm (because these objects are unimportant for the game), it is not crucial. 
	 * 
	 * @author Olga Nikitina
	 */
	public String olgarithm (Map<String,DescribedObject> describedObjects, DescribedObject target, List<String> visibleObjects){

		/*
		 * Some preparatory data structures I will need:
		 * refexp - a string for the RE
		 * distractors - a list of distractors
		 * roomContents - a list of objects inside the same room as the user
		 * det - a determiner
		 * w - the current world
		 * visible - a boolean that tells if the target is visible
		 */
//		List<String> visibleObjects;
		String refexp = "";
		ArrayList<String> distractors;
		ArrayList<String> roomContents;
		Determiner det;
		//So far, let always make determiner to be "the", because we do not refer to targets that are not visible or not unique.
		det = Determiner.THE;
		World w = target.getWorld();
		boolean visible = false;

		/* 
		 * I also need the positions of the target and of the player to compute spatial relations.
		 * orientUserTarget - the relation of the target relative to the user (i.e. the door to your right).
		 */
		Position playerPos = w.getPlayerPosition();
		Position targetPos = w.getPosition(target.getId());
		OrientationType orientUserTarget = 	GIVEUtils.GeometryToolsSpatialRelations(w, target.getId());

//		// Only consider the near objects if the user is near to the target.
//		if (w.isNear(w.getPlayerPosition(),w.getPosition(target.getId()))) {
//			visibleObjects = new ArrayList<String>();
//			for (String object : visibleObjects_param) {
//				if (w.isNear(w.getPlayerPosition(),w.getPosition(object))) {
//					visibleObjects.add(object);
//				}
//			}
//		}
//		else {
//			visibleObjects = new ArrayList<String>(visibleObjects_param);
//		}
//		
		roomContents = new ArrayList<String>(GIVEUtils.getCurrentRoomContents(w,describedObjects));
		//Somehow, we don't need the target in our room contents.
		roomContents.remove(target.getId());
		distractors = GIVEUtils.computeDistractors(describedObjects, target, visibleObjects);


		if (visibleObjects.contains(target.getId())){
			visible = true;
		}
		else{
			visible = false;
		}


		/* Now, check all properties.
		 * Construct a RE, check if it is distinctive.
		 * If yes, return it.
		 * If no, try to include different attributes in RE 
		 * and repeat the previous step.
		 */

		if(!visible){
			//just in case
			refexp = det.getArt() + " " + target.getColor().getName() + " " +  
			target.getType().getName();
			return refexp;
		}

		//general case, RE inclused colour + type of the target
		if (checkTypeAndColour(describedObjects,target, distractors)){
			if (target.getType() == ObjectType.BUTTON) {
				refexp = det.getArt() + " " + 
				target.getColor().getName() + " " +  
				target.getType().getName();
			} else {
				refexp = det.getArt() + " " + 
				target.getType().getName();	
			}

			// it appears that players remember the set of objects in the room they've seen
			// they also might get confused when they see a similar objects when they start to move to the target
			// so, to be explicit, I'm adding " that you see" to the description of the target 
			// in case there are similar objects in the room that are not visible for the user at the moment when the instruction was sent
			if (roomContents.contains(target.getId())){
				roomContents.remove(target.getId());
			}
			if (!checkTypeAndColour(describedObjects,target, roomContents)){
				refexp = refexp + " that you see";
			}
			return refexp;
		}

		//doors
		if (target.getType() == ObjectType.DOOR){
			/* Check for a RE that includes only target's position relative to the closest landmark
			 * If yes, then again find the closest landmark, calculate the relation and generate a RE
			 */
			door_with_landmark:
				if (checkPosToLandmark(describedObjects,target,distractors)){
					ArrayList<String> distrs = new ArrayList<String>(distractors);
					ArrayList<String> aux = new ArrayList<String>(distractors);
					//I don't want to have doors as landmarks for doors (because the landmark should be distinguishable from the target)
					//oops, it seems to be a double check
					for(String dist : aux){
						if (describedObjects.get(dist).getType() == ObjectType.DOOR){
							distrs.remove(dist);
						}
					}
					//find the closest landmark
					String landmarkID = findClosest(target, distrs, w);
					if (landmarkID ==""){
						break door_with_landmark;
					}

					//Find the orientation between target and the landmark.
					Position landmarkPos = w.getPosition(landmarkID);
					OrientationType relationTargetLandmark = GIVEUtils.computeSpatialRelation(targetPos,landmarkPos, playerPos);

					String refexplandmark = describedObjects.get(landmarkID).getType().getName();
					/* So far, we simply get the type of the landmark
					 * But actually we need to know if the landmark RE is distinctive. I.e., we need to use recursion.
					 */

					refexp = det.getArt() + " " + 
					target.getType().getName()+ " " + 
					relationTargetLandmark.getNameObjectLandmark() + " " + 
					det.getArt() + " " +
					refexplandmark;
					return refexp;
				}	

		if (w.getPlayerPosition().distance(targetPos) > 2){
			//the user must be far enough from the door to see it in relation to other doors

			//clear the storage for doors in the same group and the name of the position of the object in the group
			setRelexp("");
			closeDoors.clear();

			door_in_group:				
				if (checkRelPosDoors(describedObjects, target, distractors)){

					//add target to the group to find out its size
					if (!closeDoors.contains(target.getId())){
						closeDoors.add(target.getId());
					}

					int groupsize = closeDoors.size();
					//double check:door can be right, left or middle 
					if (groupsize < 4){
						refexp =  det.getArt() + " " +
						getRelexp() + " " +
						target.getType().getName() ;
					} else {
						break door_in_group;
					}
					return refexp;
				} else {
					break door_in_group;
				}
		}

		door_relation_to_user:
			if (checkPosToUser(describedObjects, target, distractors, visibleObjects) ){
				switch (orientUserTarget) {
				case BEHIND_LEFT: break door_relation_to_user;
				case BEHIND_RIGHT: break door_relation_to_user;
				default: 
					refexp =  det.getArt() + " " +
					target.getType().getName()+ " " +
					orientUserTarget.getNameUserLandmark();
					return refexp;
				}
			}

		return "oops";
		}

		//buttons
		String refexplandmark;
		String landmarkID;
		Position landmarkPos;
		Position landmarkPosOld;
		OrientationType relationTargetLandmark;

		if (target.getType() == ObjectType.BUTTON){
			//first, check the relation of the target to any landmarks that are not buttons
			button_with_landmark:
				if (checkPosToLandmark(describedObjects,target,distractors)){
					//find the closest landmark
					landmarkID = findClosest(target, distractors, w);
					if (landmarkID =="" || describedObjects.get(landmarkID).getType() == ObjectType.BUTTON){
						break button_with_landmark;
					}
					//Find the orientation between target and the landmark.
					landmarkPos = w.getPosition(landmarkID);
					relationTargetLandmark = GIVEUtils.computeSpatialRelation(targetPos,landmarkPos, playerPos);
					ArrayList<String> other_distrs = new ArrayList<String>(distractors);
					other_distrs.remove(landmarkID);
					if (checkTypeAndColour(describedObjects, describedObjects.get(landmarkID),other_distrs)) {
						refexplandmark = describedObjects.get(landmarkID).getType().getName();
					} else {
						break button_with_landmark;
					}

					refexp = det.getArt() + " " + 
					target.getColor().getName() + " " + 
					target.getType().getName()+ " " + 
					relationTargetLandmark.getNameObjectLandmark() + " " + 
					det.getArt() + " " +
					refexplandmark;

					return refexp;

				}	

		buttonTime = true;
		closeObjects.clear();
		button_with_button_landmark:
			//try to generate a RE with another button as a landmark
			if (checkPosToLandmark(describedObjects,target,distractors)){
				buttonTime = false;

				//find the closest landmark
				landmarkID = findClosest(target, distractors, w);
				if (landmarkID ==""){
					break button_with_button_landmark;
				}

				//Find the orientation between target and the landmark.
				landmarkPos = w.getPosition(landmarkID);
				relationTargetLandmark = GIVEUtils.computeSpatialRelation(targetPos, landmarkPos, playerPos);

				//use only buttons in the same group as landmarks
				fillInCloseObjects(describedObjects,target,distractors);
				ArrayList<String> other_buttons = new ArrayList<String>(closeObjects);

				//double check: basically, if there's a close landmark that is button, it should be a group of buttons,
				//but results depend on what distance one would assume as a close distance

				if (other_buttons.isEmpty()){
					break button_with_button_landmark;
				}
				//however, smth that forms a group should be close enough to be defined as the closest object
				//but just in case...
				if (other_buttons.contains(landmarkID)){
					other_buttons.remove(landmarkID);
				}

				if (!other_buttons.contains(target.getId())) { 
					other_buttons.add(target.getId());
				}

				if (checkTypeAndColour(describedObjects, describedObjects.get(landmarkID), other_buttons)){
					//so far check only if the button is unique taking into account only buttons inside the group
					refexplandmark = det.getArt() + " " + describedObjects.get(landmarkID).getColor().getName() + " one";
				} else {
					landmarkPosOld = landmarkPos;
					other_buttons.remove(target.getId());
					if (other_buttons.isEmpty()){
						break button_with_button_landmark;
					}
					landmarkID = findClosest(target, other_buttons, w);
					if (landmarkID ==""){
						break button_with_button_landmark;
					}

					relationTargetLandmark = GIVEUtils.computeSpatialRelation(targetPos, w.getPosition(landmarkID), playerPos);
					if (landmarkPosOld.distance(w.getPosition(landmarkID)) < landmarkPosOld.distance(targetPos)){

						//the new landmark should be a button from the group, 
						//either above (below) the target button or to the other side of the target button
						break button_with_button_landmark;
					}
					other_buttons.add(target.getId());
					other_buttons.remove(landmarkID);
					if (checkTypeAndColour(describedObjects, describedObjects.get(landmarkID), other_buttons)){
						//maybe the closest button on the other side will be a better landmark
						refexplandmark = det.getArt() + " " + describedObjects.get(landmarkID).getColor().getName() + " one";
					} else {

						break button_with_button_landmark;
					}
				}

				refexp = det.getArt() + " " + 
				target.getColor().getName() + " " + 
				target.getType().getName()+ " " + 
				relationTargetLandmark.getNameObjectLandmark() + " " + 
				refexplandmark;

				return refexp;

			}
		//right\left\top\bottom for buttons only

		setRelexp("");
		closeObjects.clear();
		button_group:
			if (checkRelPos(describedObjects, target, distractors)){

				if (!closeObjects.contains(target.getId())){
					closeObjects.add(target.getId());
				}

				if (!AreThereOtherGroups(describedObjects, distractors, target, w)){
					boolean AreOfSameColour = true; 
					for (String s : closeObjects){
						if (!describedObjects.get(s).getColor().equals(target.getColor())){
							AreOfSameColour=false;
						}
					}

					int groupsize = closeObjects.size();

					if (AreOfSameColour){
						refexp =  det.getArt() + " " +
						getRelexp() + " " +
						target.getType().getName() + " " +
						"in the group of "+groupsize+ " " +
						target.getColor().getName()+ " buttons";
					} else {
						refexp =  det.getArt() + " " +
						getRelexp() + " " +
						target.getType().getName() + " " +
						"in the group of "+groupsize+ " buttons";
					}

					return refexp;
				}
			} else {
				break button_group;
			}
		}

		ArrayList<String> button_distractors = new ArrayList<String>(distractors);
		for (String s : distractors){
			if (describedObjects.get(s).getType() != target.getType()){
				button_distractors.remove(s);
			}
		}
		button_close:
			if (AreFarawayButtons(describedObjects, target, button_distractors)){
				if (IsDistancePerceptible(describedObjects, target, button_distractors)) {
					boolean closest = true, furthest = true;
					for (String d : button_distractors){
						if (w.getPlayerPosition().distance(w.getPosition(target.getId()))> w.getPlayerPosition().distance(w.getPosition(d)) ){
							closest = false;
						}
						if (w.getPlayerPosition().distance(w.getPosition(target.getId()))< w.getPlayerPosition().distance(w.getPosition(d)) ){
							furthest = false;
						}
					}
					boolean colour = false;
					for (String d : button_distractors){
						if (describedObjects.get(d).getColor() == target.getColor()){
							colour = true;
						}
					}	
					if (colour) {
						if (closest && !furthest){
							refexp =  det.getArt() + " closest " +
							target.getColor().getName() + " " +
							target.getType().getName();
						} else
							if (!closest && furthest){
								refexp =  det.getArt() + "  most distant " +
								target.getColor().getName() + " " +
								target.getType().getName();
							} else {
								break button_close;
							}
					} else {
						if (closest && !furthest){
							refexp =  det.getArt() + " closest " +
							target.getType().getName();
						} else
							if (!closest && furthest){
								refexp =  det.getArt() + "  most distant " +
								target.getType().getName();
							} else {
								break button_close;
							}
					}
					return refexp;
				}
			}
		return "oops";
	}

	private boolean IsDistancePerceptible(Map<String, DescribedObject> describedObjects, DescribedObject target, ArrayList<String> distractors) {
		//distance between similar objects in the room should be big enough, that user could easily understand which object is the closest one.
		World w = target.getWorld();
		double[] distances = new double[distractors.size()+1];
		int i = 0;
		for (String d : distractors){
			distances[i] = w.getPlayerPosition().distance(w.getPosition(d));
			i = i+1;
		}
		distances[distances.length-1] = w.getPlayerPosition().distance(w.getPosition(target.getId()));
		for (int j = 0; j<distances.length; j++){
			for (int k = 0; k<distances.length; k++){
				if (java.lang.Math.abs(distances[j]-distances[k])<1.5 && k!=j){
					return false;	
				}
			}
		}
		return true;
	}

	private boolean AreFarawayButtons(Map<String, DescribedObject> describedObjects,DescribedObject target, ArrayList<String> distractors) {
		World w = target.getWorld();
		for (String d : distractors){
			if (w.getPosition(target.getId()).distance(w.getPosition(d)) < 1.5){
				return false;
			}
		}
		return true;
	}

	public String fallbackRE(DescribedObject target) {
		Determiner det = Determiner.THE;
		String refexp;
		if (target.getType() == ObjectType.BUTTON) {
			refexp = det.getArt() + " " + target.getColor().getName() + " " + target.getType().getName();
		}else{
			refexp = det.getArt() + " " + target.getType().getName();
		}

		return refexp;
	}
	public void setRelexp (String relexp){
		this.relexp = relexp;
	}
	public String getRelexp(){
		return this.relexp;
	}
	private boolean AreThereOtherGroups (Map<String,DescribedObject> describedObjects, ArrayList<String> distractors, DescribedObject target, World w){
		ArrayList<String> otherButtons = new ArrayList<String>(distractors);

		for (String dist : distractors){
			if (closeObjects.contains(dist)){
				otherButtons.remove(dist);
			}
		}
		for (String dist : distractors){
			if (!describedObjects.get(dist).getRoom().equals(describedObjects.get(target.getId()).getRoom())){
				otherButtons.remove(dist);
			}
		}

		for (String button1ID : otherButtons){
			ArrayList<String> otherButtons2 = new ArrayList<String>(otherButtons);
			otherButtons2.remove(button1ID);
			if(target.getType()==describedObjects.get(button1ID).getType()){
				for (String button2ID : otherButtons2){
					if(target.getType()==describedObjects.get(button2ID).getType()){
						if (w.getPosition(button1ID).distance(w.getPosition(button2ID))< 1.5){
							return true;
						}
					}
				}
			}
			otherButtons2.add(button1ID);
		}
		return false;

	}

	private boolean checkRelPos(Map<String,DescribedObject> describedObjects, DescribedObject target, List<String> distractors){
		String relexp = "";
		World w = target.getWorld();
		double targY = w.getPosition(target.getId()).getY();
		double distY;
		boolean isColumn = false, isLine = false;
		boolean left = true, right = true, top = true, bottom = true;
		fillInCloseObjects(describedObjects, target, distractors);
		if (closeObjects.isEmpty()){
			return false;
		}
		//top-bottom
		for (String s : closeObjects){
			distY =  w.getPosition(s).getY();

			if (java.lang.Math.abs(distY-targY)>0.01){
				isColumn = true;
			}

			if (distY>targY){
				top = false;
				break;
			}
		}

		for (String s : closeObjects){
			distY =  w.getPosition(s).getY();
			if (distY<targY){
				bottom = false;
				break;
			}
		}

		//left-right
		double anglePlayerTarg = w.getPosition(target.getId()).getOrientationTo(w.getPlayerPosition()).getAngleTo(w.getPlayerOrientation());
		for (String s : closeObjects){
			double anglePlayerDist =  w.getPosition(s).getOrientationTo(w.getPlayerPosition()).getAngleTo(w.getPlayerOrientation());
			if (w.getPosition(s).getX()!=w.getPosition(target.getId()).getX() || 
					w.getPosition(s).getZ()!=w.getPosition(target.getId()).getZ()){
				isLine = true;
			}
			if (anglePlayerDist<0 && anglePlayerTarg<0){
				if (anglePlayerDist>anglePlayerTarg){
					left = false;
					break;
				}
			}
			if (anglePlayerDist>0 && anglePlayerTarg>0){
				if (anglePlayerDist>anglePlayerTarg){
					left = false;
					break;
				}
			}

			if (anglePlayerDist<0 && anglePlayerTarg>0){
				left = false;
				break;
			}
		}

		for (String s : closeObjects){
			double anglePlayerDist =  w.getPosition(s).getOrientationTo(w.getPlayerPosition()).getAngleTo(w.getPlayerOrientation());
			if (anglePlayerDist<0 && anglePlayerTarg<0){
				if (anglePlayerDist<anglePlayerTarg){
					right = false;
					break;
				}

			}
			if (anglePlayerDist>0 && anglePlayerTarg>0){
				if (anglePlayerDist<anglePlayerTarg){
					right = false;
					break;
				}
			}

			if (anglePlayerDist>0 && anglePlayerTarg<0){
				right = false;
				break;
			}
		}
		//middle

		ArrayList<String> targetRow = new ArrayList<String>();
		ArrayList<String> targetColumn = new ArrayList<String>();
		for (String d : closeObjects){
			if (w.getPosition(d).getY() == w.getPosition(target.getId()).getY() && !d.equals(target.getId())){
				targetRow.add(d);
			}
		}
		for (String d : closeObjects){
			if (w.getPosition(d).getZ() == w.getPosition(target.getId()).getZ() && 
					w.getPosition(d).getX() == w.getPosition(target.getId()).getX()&& !d.equals(target.getId())){
				targetColumn.add(d);
			}
		}

		boolean middleInRow = false;
		boolean middleInColumn = false;

		if (targetColumn.size() == 2 && !top && !bottom){
			middleInColumn = true;
		}

		if (targetRow.size() == 2 && !left && !right){
			middleInRow = true;
		}

		//set the relexp

		if (isLine){

			if (right && !left){
				relexp = "left";
				setRelexp(relexp);
			}
			if (left && !right){
				relexp = "right";
				setRelexp(relexp);
			}
			if (middleInRow){
				relexp = "middle";
				setRelexp(relexp);
			}

		}

		if(isLine && isColumn){
			relexp = relexp + " ";
		}
		if (isColumn){
			if (top && !bottom){
				relexp = relexp + "top";
				setRelexp(relexp);
			}
			if (bottom && !top){
				relexp = relexp + "bottom";
				setRelexp(relexp);
			}
			if (middleInColumn){
				relexp =  relexp + "middle";
				setRelexp(relexp);
			}

		}

		if (middleInRow && middleInColumn){
			relexp = "center";
			setRelexp(relexp);
		}

		if ((left==false && right==false && middleInRow == false) || (top==false && bottom==false && middleInColumn == false)) {
			//the target button is somewhere in the middle of the group
			return false;
		} else {
			return true;
		} 
	}
	private boolean checkRelPosDoors(Map<String,DescribedObject> describedObjects, DescribedObject target, List<String> distractors){
		String relexp = "";
		World w = target.getWorld();
		boolean left = true, right = true, middle = true;
		fillInCloseDoors(describedObjects, target, distractors);
		if (closeDoors.isEmpty()){
			return false;
		}

		//left-right
		double anglePlayerTarg = w.getPosition(target.getId()).getOrientationTo(w.getPlayerPosition()).getAngleTo(w.getPlayerOrientation());
		for (String s : closeDoors){
			double anglePlayerDist =  w.getPosition(s).getOrientationTo(w.getPlayerPosition()).getAngleTo(w.getPlayerOrientation());

			if (anglePlayerDist<0 && anglePlayerTarg<0){
				if (anglePlayerDist>anglePlayerTarg){
					left = false;
					break;
				}
			}
			if (anglePlayerDist>0 && anglePlayerTarg>0){
				if (anglePlayerDist>anglePlayerTarg){
					left = false;
					break;
				}
			}

			if (anglePlayerDist<0 && anglePlayerTarg>0){
				left = false;
				break;
			}
		}

		for (String s : closeDoors){
			double anglePlayerDist =  w.getPosition(s).getOrientationTo(w.getPlayerPosition()).getAngleTo(w.getPlayerOrientation());
			if (anglePlayerDist<0 && anglePlayerTarg<0){
				if (anglePlayerDist<anglePlayerTarg){
					right = false;
					break;
				}

			}
			if (anglePlayerDist>0 && anglePlayerTarg>0){
				if (anglePlayerDist<anglePlayerTarg){
					right = false;
					break;
				}
			}

			if (anglePlayerDist>0 && anglePlayerTarg<0){
				right = false;
				break;
			}
		}
		//middle

		if (closeDoors.size() > 2 && !left && !right){
			middle = false;
		}

		//set the relexp


		if (right && !left){
			relexp = "left";
			setRelexp(relexp);
		} else
			if (left && !right){
				relexp = "right";
				setRelexp(relexp);
			} else
				if (middle){
					relexp = "middle";
					setRelexp(relexp);
				} 



		if (left==false && right==false && middle == false) {
			//the target door is somewhere in the middle of the group
			return false;
		} else {
			return true;
		} 
	}

	//checks if a RE colour + type is usable
	private  boolean checkTypeAndColour(Map<String,DescribedObject> describedObjects, DescribedObject target, List<String> distractors){
		if (distractors.isEmpty()){
			return true;
		}
		for (String d: distractors){
			DescribedObject di = describedObjects.get(d);
			if (di.getType() == target.getType() && 
					di.getColor() == target.getColor()) {
				return false;
			}			
		}
		return true;

	}
	private  boolean checkPosToUser(Map<String,DescribedObject> describedObjects,DescribedObject target, List<String> distractors, List<String> visibleObjects){
		//Checks if a RE target + relation-to-user  is usable 
		World w = target.getWorld();
		OrientationType orientUserDistractor;
		OrientationType orientUserTarget = 	GIVEUtils.GeometryToolsSpatialRelations(w, target.getId());
		if (distractors.isEmpty()){
			return true;
		}
		for (String d: distractors){

			orientUserDistractor = GIVEUtils.GeometryToolsSpatialRelations(w, d);
			DescribedObject dist = describedObjects.get(d);
			if (dist.getType() == target.getType() && 
					dist.getColor() == target.getColor()&&
					orientUserDistractor == orientUserTarget) {
				return false;
			} 
		}
		return true;
	}

	private  boolean checkPosToLandmark(Map<String,DescribedObject> describedObjects,DescribedObject target, List<String> distractors){
		// Checks if a RE target + relation-to-landmark is usable
		World w = target.getWorld();
		Position playerPos = w.getPlayerPosition();
		Position targetPos = w.getPosition(target.getId());
		String landmarkID = findClosest(target, distractors, w);
		//if there is no close landmark, return false
		if (landmarkID == ""){
			return false;
		}
		Position landmarkPos = w.getPosition(landmarkID);
		OrientationType relationDistractorLandmark;	

		//if there are no close landmarks, return false
		if (GIVEUtils.computeCloseLandmarks(target, distractors).isEmpty()){
			return false;
		}
		//for relation to landmarks, Markus'es method is used, 
		//because in this case the orientation of the target and landmark doesn't matter
		OrientationType relationTargetLandmark = GIVEUtils.computeSpatialRelation(targetPos,landmarkPos, playerPos);

		//don't use buttons as landmarks, while it is possible
		if (!buttonTime && describedObjects.get(landmarkID).getType() == ObjectType.BUTTON){
			return false;
		}
		// check if there is a distractor for which the same relation holds
		for (String d: distractors){
			if (!d.equals(landmarkID)){
				Position distractorPos = w.getPosition(d);
				relationDistractorLandmark = GIVEUtils.computeSpatialRelation(distractorPos, landmarkPos, playerPos);
				DescribedObject di = describedObjects.get(d);
				if (di.getType() == target.getType() && 
						di.getColor() == target.getColor()&& 
						relationDistractorLandmark == relationTargetLandmark) {
					// if such distractor exists, 
					//target should be closer to the landmark, than the distractor and
					//the angle between the distractor and the target should be smaller than half pi
					// (to understand the last condition, draw a number of concave corners and close parallel walls with buttons on them)

					double distToLand = distractorPos.distance(landmarkPos);
					double targToLand = targetPos.distance(landmarkPos);
					double angle = java.lang.Math.PI / 2;
					double greaterhalfpi = (java.lang.Math.PI / 2) + 0.1;
					//basically, two buttons can be on the wall one above the other
					//in this case it is not quite clear, which is closer,
					// so I return false in such cases (distance wouldn't help)
					if (distractorPos.getX() == targetPos.getX() && distractorPos.getZ() == targetPos.getZ()){
						return false;
					}
					if (buttonTime || target.getType() == ObjectType.DOOR) {
						angle = w.getOrientation(d).getAngleTo(w.getOrientation(target.getId()));
					}
					if (distToLand<=targToLand || java.lang.Math.abs(angle) > greaterhalfpi){
						return false;

					}
				}
			}
		}
		return true;
	}


	/*
	 * Nota bene: a RECURSIVE method
	 */

	private void fillInCloseObjects (Map<String,DescribedObject> describedObjects, DescribedObject target, List<String> distractors){
		World w = target.getWorld();
		ArrayList<String> auxiliary = new ArrayList<String>(distractors);
		if (target.getType() == ObjectType.BUTTON){
			for (String d : auxiliary){
				if (describedObjects.get(d).getType() == ObjectType.BUTTON){
					if (w.getPosition(target.getId()).distance(w.getPosition(d))< 1.5){
						if (describedObjects.get(d).getRoom().equals(describedObjects.get(target.getId()).getRoom())) {
							if (!closeObjects.contains(d)){
								closeObjects.add(d);
								//now, call this method for the distractor d. For this, remove it from the set of distractors.
								distractors.remove(d);
								fillInCloseObjects(describedObjects, describedObjects.get(d), distractors);
								//Done with the distractor d? Add it back!
								distractors.add(d);
							}					
						}
					}
				}
			}
		}
	}


	/*
	 * Nota bene: a RECURSIVE method
	 */

	private void fillInCloseDoors (Map<String,DescribedObject> describedObjects, DescribedObject target, List<String> distractors){
		World w = target.getWorld();
		ArrayList<String> roomContents = new ArrayList<String>(GIVEUtils.getCurrentRoomContents(w,describedObjects));
		ArrayList<String> auxiliary = new ArrayList<String>(distractors);
		if (target.getType() == ObjectType.DOOR){
			for (String d : auxiliary){
				if (describedObjects.get(d).getType() == ObjectType.DOOR){
					if (w.getPosition(target.getId()).distance(w.getPosition(d))< 4.0){
						if (roomContents.contains(d)) {
							if (!closeDoors.contains(d)){
								closeDoors.add(d);
								//now, call this method for the distractor d. For this, remove it from the set of distractors.
								distractors.remove(d);
								fillInCloseDoors(describedObjects, describedObjects.get(d), distractors);
								//Done with the distractor d? Add it back!
								distractors.add(d);
							}					
						}
					}
				}
			}
		}
	}

	/**
	 * I've taken a part of genSpatialRexp by Markus to make a method that finds the closest landmark
	 * 
	 * @ author Markus Draeger, Olga Nikitina
	 */
	private  String findClosest(DescribedObject target, List<String> distractors, World w) {

		String landmark = "";
		double maxDist = 1.9;
		HashMap<String,Double> closeLandmarks = new HashMap<String, Double>();
		closeLandmarks = GIVEUtils.computeCloseLandmarks(target, distractors);
		if (closeLandmarks.isEmpty()){
			return ""; 
		}
		for(String l : closeLandmarks.keySet()){
			if(closeLandmarks.get(l) <= maxDist){
				landmark = l;
				maxDist = closeLandmarks.get(l);
			}
		}
		return landmark;
	}

}
